{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findmax(A,minloc,maxloc):\n",
    "\tif maxloc==minloc:\t\n",
    "\t\treturn(minloc, maxloc, A[minloc])#若数组里只有一个元素，则返回该元素\n",
    "\telse:\n",
    "\t\tmid=(minloc+maxloc)//2 #找出中间位置\n",
    "\t\t(left_low,left_high,left_sum)=findmax(A,minloc,mid)\n",
    "\t\t(right_low,right_high,right_sum)=findmax(A,mid+1,maxloc)\n",
    "\t\t(cross_low,cross_high,cross_sum)=findmid(A,minloc,mid,maxloc)\n",
    "\t\tif left_sum>=right_sum and left_sum>=cross_sum:\n",
    "\t\t\treturn (left_low,left_high,left_sum)\n",
    "\t\telif right_sum>=left_sum and right_sum>=cross_sum:\n",
    "\t\t\treturn (right_low,right_high,right_sum)\n",
    "\t\telse:\n",
    "\t\t\treturn (cross_low,cross_high,cross_sum)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findmid(A, minloc, midloc, maxloc):\n",
    "    INF=2000\n",
    "    left_SUM=-INF \n",
    "    temp=0\n",
    "    min_left=midloc \n",
    "    for i in range(midloc,minloc,-1):\n",
    "        temp=temp+A[i] \n",
    "        if temp>left_SUM:\n",
    "            left_SUM=temp\n",
    "            min_left=i \n",
    "    right_SUM=-INF\n",
    "    temp=0\n",
    "    max_right=midloc+1\n",
    "    for j in range(midloc+1,maxloc):\n",
    "        temp=temp+A[j]\n",
    "        if temp>right_SUM:\n",
    "            right_SUM=temp\n",
    "            max_right=j\n",
    "    return min_left,max_right,left_SUM+right_SUM\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[4, -1, 2, 1]\n6\n"
     ]
    }
   ],
   "source": [
    "A=[-2,-1,-3,4,-1,2,1,-5,4]\n",
    "minloc,maxloc,SUM=findmax(A,0,len(A)-1)\n",
    "print(A[minloc:maxloc+1])\n",
    "print(SUM)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}